#include <stdio.h>
#include <string.h>
#include "../common.h"

#define MaxVertexNum 100


//类型定义
typedef int VertexType;
typedef int EdgeType;

struct _Graph;
typedef void (*_inflate) (struct _Graph*,EdgeType**,int);
typedef void (*_print) (struct _Graph*);
typedef int (*_firstNeighbor) (struct _Graph*,int);
typedef void (*_mstPrim) (struct _Graph*,VertexType);
typedef void (*_dijkstra) (struct _Graph*,VertexType);

//函数申明
int static FirstNeighbor (struct _Graph* G,int v);
void static Print (struct _Graph* G);
void static Inflate (struct _Graph* G,EdgeType** edge,int n);
void static MstPrim(struct _Graph* G,int v);
int static LowCostVertex(bool isJoin[], EdgeType lowCost[],int n);
void static Dijkstra (struct _Graph* G,VertexType v);

//图的定义（邻接矩阵存储)
typedef struct _Graph{
    VertexType Vex[MaxVertexNum];//顶点
    EdgeType Edge[MaxVertexNum][MaxVertexNum];//边
    int VertexNum;//顶点个数

    _inflate inflate;
    _print print;//打印邻接矩阵
    _firstNeighbor firstNeighbor;
    _mstPrim mstPrim;//Prim算法求取最小生成树
    _dijkstra dijkstra;//dijkstra算法求取单源最短路径

} *Graph;


//图的操作
/*
 * Dijkstra算法求解单源最短路径
 * 1. 用初始顶点初始化final数组与dist数组
 * 2. 更新final中为false的顶点的dist与path
*/
void Dijkstra(Graph G, int v){
    //初始化辅助数组
    bool final[G->VertexNum];
    memset(final,false,sizeof(bool)*G->VertexNum);
    final[v] = true;
    EdgeType dist[G->VertexNum];
    memcpy(dist,G->Edge[v],sizeof(VertexType)*G->VertexNum); 
    int path[G->VertexNum];
    for(int i = 0; i < G->VertexNum; i++){
        path[i] = v;
    }
    path[v] = -1;//源点到自己的最短路径的前置顶点为-1,表示没有前置顶点

    int joinedNum = 0;//每加入一个顶点,joinedNum就加1。用于结束循环
    int minVertex;//最小代价顶点
    printf("依次选取的顶点顺序:%d ",v);
    while(joinedNum < G->VertexNum -1){
        //求解最小代价顶点
        minVertex = LowCostVertex(final,dist,G->VertexNum);
        final[minVertex] = true;
        printf("%d ",minVertex);
        //更新dist与path
        for(int i = 0; i < G->VertexNum; i++){
            if(final[i] == false && dist[i] > dist[minVertex] + G->Edge[minVertex][i]){ //(与Prim算法不相同的部分!!!!)
                dist[i] = dist[minVertex] + G->Edge[minVertex][i];
                path[i] = minVertex;
            }
        }
        
        joinedNum++;
    }
    printf("\n");
    printf("dist数组:");
    for (int i = 0; i < G->VertexNum; i++)
    {
        printf("%d ",dist[i]);
    }
    printf("\npath数组:");
    for (int i = 0; i < G->VertexNum; i++)
    {
        printf("%d ",path[i]);
    }
    printf("\n");
    
}

/*
 * Prim算法求取最小生成树
1.用初始顶点初始化isJoin数组与lowCost数组
2.从lowCost数组中选取代价最小且isJoin为false的顶点v，然后更新lowCost，随后isJoin[v] = true
3.循环第2步直到isJoin全为true
* */
void MstPrim(Graph G,int v){
    //初始化辅助数组
    bool isJoin[G->VertexNum];
    memset(isJoin,false,sizeof(bool)*G->VertexNum);
    isJoin[v] = true;
    EdgeType lowCost[G->VertexNum];
    memcpy(lowCost,G->Edge[v],sizeof(VertexType)*G->VertexNum); 
    
    int joinedNum = 0;//每加入一个顶点,joinedNum就加1。用于结束循环
    int minVertex;//最小代价顶点
    printf("依次选取的顶点顺序:%d ",v);
    while(joinedNum < G->VertexNum -1){
        //求解最小代价顶点
        minVertex = LowCostVertex(isJoin,lowCost,G->VertexNum);
        isJoin[minVertex] = true;
        printf("%d ",minVertex);
        // printf("最小代价顶点：%d\n",minVertex);
        //更新lowCost
        for(int i = 0; i < G->VertexNum; i++){
            if(isJoin[i] == false && lowCost[i] > G->Edge[minVertex][i]){
                lowCost[i] = G->Edge[minVertex][i];
            }
        }
        
        joinedNum++;
    }
    printf("\n");
    printf("lowCost数组:");
    for (int i = 0; i < G->VertexNum; i++)
    {
        printf("%d ",lowCost[i]);
    }
    
}
int LowCostVertex(bool isJoin[], EdgeType lowCost[],int n){
    EdgeType min;
    int index;
    for(int i = 0; i < n; i++){
        if(isJoin[i] == false){
            min = lowCost[i];
            index = i;
            break;
        }
    }

    for(int i = 0; i < n; i++){
        if (isJoin[i] == false && lowCost[i] < min){
            min = lowCost[i];
            index = i;
        }
    }
    return index;
}



/*拷贝边数组*/
void Inflate (Graph G, EdgeType** edge,int n){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            G->Edge[i][j] = edge[i][j];
        }
    }
    G->VertexNum = n;
}

/*打印邻接矩阵*/
void Print(Graph G){
    printf("\n**************************\n");
    for(int i=0; i < G->VertexNum; i++){
        for(int j = 0; j < G->VertexNum; j++){
            printf("%-4d",G->Edge[i][j] == INF?-1:G->Edge[i][j]);
        }
        printf("\n");
    }
    printf("***************************\n");
}

/*寻找顶点v的第一个邻接点，找不到则返回-1*/
int FirstNeighbor(Graph G,int v){
    if(v>=MaxVertexNum){
        return -1;
    }
    
    int w=0;
    for(EdgeType *p = G->Edge[v]; p < G->Edge[v+1]; p++,w++){
        if(*p != 0){
            return w; 
        }
    }

    return -1;
}

//预定义变量，方便使用
#ifdef USING_BUILDIN_GRAPH_VAR
struct _Graph G = {
    .Edge = {
        {0,1,4,4,6,5},
        {1,0,5,INF,INF,6},
        {4,5,0,2,INF,INF},
        {4,4,2,0,6,INF},
        {6,INF,INF,6,0,3},
        {5,6,INF,INF,3,0}
    },
    .VertexNum = 6,
    //以下函数指针不应修改
    .inflate = Inflate,
    .print = Print,
    .firstNeighbor = FirstNeighbor,
    .mstPrim = MstPrim,
    .dijkstra = Dijkstra,
};
#endif

